The present invention generally relates to I/O devices. More specifically, the present invention relates to a novel apparatus that merges a plurality of data streams into a single data stream.
In an effort to increase I/O bandwidth in high performance processor based systems, a number of companies have developed the HyperTransport (xe2x80x9cHTxe2x80x9d) I/O interconnect structure. Briefly, the HT I/O bus structure is a scalable device level architecture that provides a significant increase in transaction throughput over existing I/O bus architectures such as Peripheral Component Interconnect (xe2x80x9cPCIxe2x80x9d) and Advanced Graphics Port (xe2x80x9cAGPxe2x80x9d).
The foundation of the HT I/O bus is dual point-to-point unidirectional links consisting of a data path, control signals, and clock signals. The HT I/O bus can provide both point-to-point links and a scalable network topology using HT I/O switching fabrics. Thus, an HT based system can be expanded using HT switches to support multilevel, highly complex systems.
Communications between multiple HT I/O devices are known as data streams. Each data stream contains one or more packets of information. Each packet of information contains a packet ID and a data payload. The packet ID is also commonly referred to as a unit ID. Because all packets are transferred to or from a host bridge, the packet ID provides information that can be utilized to determine the source or destination of the packet. A more detailed description of the HT I/O bus structure is presented in Appendix A.
FIG. 1 presents an HT I/O device 100 that interfaces with a first unidirectional link 110 and a second unidirectional link 120. Thus, the HT I/O device 100 can receive input data streams and transmit output data streams via unidirectional links 110 and 120. The HT I/O device 100 contains input ports 130 and 150 for receiving data streams and output ports 140 and 160 for transmitting data streams. The HT device 100 may also contain circuitry for generating packets that can be transmitted as output data streams via the output ports 140 and 160.
HT I/O devices may also be daisy chained as shown in FIG. 2. FIG. 2 presents a portion of a single unidirectional link in an HT I/O bus. The unidirectional link shown contains three HT I/O devices 210, 220, and 230. If the first HT I/O device 210 receives a data stream with a destination ID that is equal to the ID of the first HT I/O device 210, then the first HT I/O device 210 will receive and internally process the data stream. However, if the destination ID is not equal to the ID of the first HT I/O device 210, then the first HT I/O device 210 will forward the data stream to the second HT I/O device 220.
As the first HT I/O device 210 may also have the capability to generate packets, the output data stream of the first HT I/O device 210 is a composite of the input packet stream received by the first HT I/O device 210 and the internally generated packets. These internally generated packets will be referred to as an internal data stream.
The data stream received by the first HT I/O device 210 and the device""s internal data stream may vary with time. For example, the input data stream for the first HT I/O device 210 may contain no packets over a given time interval. Thus, all packets in the internal data stream generated during that time interval by the first HT I/O device 210 may be transmitted through the first HT I/O device""s output port. Alternately, if the data stream received by the first HT I/O device 210 and the device""s internal data stream both contain a large number of packets, the HT I/O device may be required to choose between forwarding the received data stream or outputting the internally generated packets. The process by which such a choice is made is known in the art as a forwarding fairness algorithm.
Prior art systems allow an HT I/O device to insert internally generated packets into an output data stream freely if the output data stream is empty. However, if the output data stream contains a large number of packets, the prior art systems only allow the HT I/O device to insert internally generated packets into the output data stream at a rate that is not greater than the rate that the HT I/O device is receiving and forwarding packets from another HT I/O device. Such prior art systems are not optimal. Thus, a more optimal apparatus for merging two data streams into a single data stream is needed.
One embodiment of the invention is an I/O device that includes: an input port; an input buffer coupled to the input port; an internal port operable to store packets generated by the I/O device; an internal buffer coupled to the internal port; a plurality of packet ID arrival registers coupled to the input port and the internal port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the input buffer and the internal buffer; and an output port coupled to the packet selector.
In another embodiment of the invention, the arbiter includes an autocorrelation magnitude table.
In another embodiment of the invention, the arbiter includes a maximum autocorrelation magnitude table.
In another embodiment of the invention, the arbiter is operable to command the packet selector to select a packet from one of the plurality of input buffers based upon the output of the autocorrelation logic.
Another embodiment of the invention is an I/O device that includes: a first input port; a first input buffer coupled to the first input port; a second input port; a second input buffer coupled to the second input port; a plurality of packet ID arrival registers coupled to the first input port and the second input port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the first input buffer and the second input buffer; and an output port coupled to the packet selector.
Another embodiment of the invention is an I/O device that includes: a first internal port operable to store packets generated by the I/O device; a first internal buffer coupled to the first internal port; a second internal port operable to store packets generated by the I/O device; a second internal buffer coupled to the second internal port; a plurality of packet ID arrival registers coupled to the first internal port and the second internal port; autocorrelation logic coupled to the plurality of packet ID arrival registers; an arbiter coupled to the autocorrelation logic; a packet selector coupled to the arbiter, the first internal buffer and the second internal buffer; and an output port coupled to the packet selector.
Another embodiment of the invention is an HT I/O device that includes: an input port; an input buffer coupled to the input port; an internal port for storing packets generated by the HT I/O device; an internal buffer coupled to the internal port; and a plurality of packet ID arrival registers coupled to the input port and the internal port.